package com.company.algo.niuke;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * 字节：设计LRU缓存结构
 * 设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
 * set(key, value)：将记录(key, value)插入该结构
 * get(key)：返回key对应的value值
 * [要求]
 * set和get方法的时间复杂度为O(1)
 * 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
 * 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
 * 若opt=1，接下来两个整数x, y，表示set(x, y)
 * 若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
 * 对于每个操作2，输出一个答案
 */
public class LRU {
    /**
     * lru design
     *
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    HashMap<Integer, Integer> container = new HashMap<>();
    HashMap<Integer, Integer> freq = new HashMap<>();
    int maxFreq = 1;
    public int[] LRU(int[][] operators, int k) {
        //需要维护key,value和操作频率Tuple{key,value,freq}，当记录操过k时，删除freq最小的记录
        List<Integer> res = new ArrayList<>();
        for (int[] operator : operators) {
            if (operator[0] == 1) {       //添加操作
                //校验是否需要删除元素
                if (container.size() == k) deleteLeastUse();
                int key = operator[1];
                int value = operator[2];
                container.put(key, value);
                freq.put(key,++maxFreq);    //修改后的元素作为最高频
            } else if (operator[0] == 2) {  //取值操作
                int key = operator[1];
                res.add(container.getOrDefault(key, -1));
                freq.put(key,++maxFreq);    //取值后的元素作为最高频
            } else {
                throw new RuntimeException("error input");
            }
            System.out.print(container);
            System.out.print(freq);
            System.out.println();
        }
        int[] ret = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ret[i] = res.get(i);
        }
        return ret;
    }

    private void deleteLeastUse() {
        int minVal = maxFreq;
        int removeK = -1;
        for (int k : freq.keySet()) {
            if (minVal > freq.get(k)) {
                minVal = freq.get(k);
                removeK = k;
            }
        }
        container.remove(removeK);
        freq.remove(removeK);
    }

    public static void main(String[] args) {
        LRU Main = new LRU();
        int[][] operators = new int[6][];
        operators[0] = new int[]{1,1,1};
        operators[1] = new int[]{1,2,2};
        operators[2] = new int[]{1,3,2};
        operators[3] = new int[]{2,1};
        operators[4] = new int[]{1,4,4};
        operators[5] = new int[]{2,2};
        int k = 3;
        System.out.println(Arrays.toString(Main.LRU(operators, k)));
    }

}
